class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for i in range(len(nums)):
            if nums[i]>0 and nums[i]!=i+1:
                # traverse
                index = nums[i]-1
                tmp = nums[i]
                while 0<=index<len(nums) and nums[index]!=tmp:
                    t = nums[index]
                    nums[index]=tmp
                    tmp=t
                    index = tmp-1
        for i in range(len(nums)):
            if nums[i]==i+1:continue
            else:return i+1
        return len(nums)+1

print(Solution().firstMissingPositive([1]))